package com.bo.day20241121;

import java.util.ArrayList;
import java.util.Collection;
import java.util.List;
import java.util.Comparator;
import java.util.HashMap;

/**
 * @Author: gpb
 * @Date: 2024/11/27 15:31
 * @Description:
 */
public class TopologicalOrderDFS1 {
    // 不要提交这个类
    public static class DirectedGraphNode {
        public int label;
        public ArrayList<DirectedGraphNode> neighbors;

        public DirectedGraphNode (int x) {
            label = x;
            neighbors = new ArrayList<DirectedGraphNode>();
        }
    }

    /**
     * 记录每个节点的深度
     */
    public static class Record {
        public DirectedGraphNode node;
        public int deep;

        public Record (DirectedGraphNode node, int nodes) {
            this.node = node;
            this.deep = nodes;
        }
    }

    /**
     * 比较器
     * x的节点数>=y的节点数，则x的拓扑序序更小
     */
    public static class RecordComparator implements Comparator<Record> {
        @Override
        public int compare (Record o1, Record o2) {
            return o2.deep - o1.deep;
        }
    }

    public static ArrayList<DirectedGraphNode> topSort (ArrayList<DirectedGraphNode> graph) {
        HashMap<DirectedGraphNode, Record> inMap = new HashMap<>();
        for (DirectedGraphNode directedGraphNode : graph) {
            f(directedGraphNode, inMap);
        }
        List<Record> records = new ArrayList<>(inMap.values());
        records.sort(new RecordComparator());
        ArrayList<DirectedGraphNode> result = new ArrayList<>();
        for (Record record : records) {
            result.add(record.node);
        }
        return result;
    }

    public static Record f (DirectedGraphNode node, HashMap<DirectedGraphNode, Record> inMap) {
        if (inMap.containsKey(node)) {
            return inMap.get(node);
        }
        int deep = 0;
        for (DirectedGraphNode directedGraphNode : node.neighbors) {
            deep = Math.max(deep, f(directedGraphNode, inMap).deep + 1);
        }
        Record record = new Record(node, deep);
        inMap.put(node, record);
        return record;
    }
}
